﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm
{
    class FastMatrixExponentiation
    {
        public FastMatrixExponentiation()
        {
            int testCase = Int32.Parse(TestConsole.ReadLine());
            while (testCase-- > 0)
            {
                
                string[] input = TestConsole.ReadLine().Split(' ');
                int size = Int32.Parse(input[0]);
                int p = Int32.Parse(input[1]);
                Dictionary<int, ulong[,]> exp = new Dictionary<int, ulong[,]>();
                exp[1] = new ulong[size,size];
                for (int i = 0; i < size; i++)
                {
                    input = TestConsole.ReadLine().Split(' ');
                    for (int j = 0; j < size; j++)
                    {
                        exp[1][i, j] = ulong.Parse(input[j]);
                    }
                }
                int leftP = p;
                int upP = 1;
                while (upP * 2 < leftP)
                {
                    exp[upP * 2] = Multiply(exp[upP], exp[upP], size);
                    upP *= 2;
                }
                leftP -= upP;
                int downP = upP;
                while (leftP > 0 && downP > 0)
                {
                    if (leftP > downP)
                    {
                        exp[upP + downP] = Multiply(exp[upP], exp[downP], size);
                        leftP -= downP;
                        upP += downP;
                    }
                    else
                    {
                        downP /= 2;
                    }
                }
                while (upP < p)
                {
                    exp[upP + 1] = Multiply(exp[upP], exp[1], size);
                    upP++;
                }
                for (int i = 0; i < size; i++)
                {
                    for (int j = 0; j < size; j++)
                    {
                        Console.Write((exp[p][i, j] % 10007) + " ");
                    }
                    Console.Write("\n");
                }
                Console.WriteLine("");
            }
        }
        private ulong[,] Multiply(ulong[,] a, ulong[,] b, int size)
        {
            ulong[,] c = new ulong[size, size];
            for (int x = 0; x < size; x++)
            {
                for (int y = 0; y < size; y++)
                {
                    ulong v = 0;
                    for (int z = 0; z < size; z++)
                    {
                        v += a[z, x] * b[y, z];
                    }
                    c[y, x] = v;
                }
            }
            return c;
        }
    }
}
